package haxe.util;

import haxe.util.benchmark.TestData;
import haxe.util.Compare;


class Sorting
{
	public static function fastSort( a:Array<Dynamic>, ?comp:Comparator<Dynamic> ):Void
	{
		#if flash9
			a.sort( comp.compare );
		#else true
			Sorting.quicksort( a, comp );
		#end
	}
	
	public static function mergeSort( a:Array<Dynamic>, ?comp:Comparator<Dynamic>, ?p:Int, ?q:Int ):Void
	{
		if ( p == null) p = 0;
		if (q == null ) q = a.length - 1;
		if ( comp == null ) comp = Comparators.getComparator( a[0] );
		Sorting.johnVonNeumann( a , comp, p, q );
	}
	
	public static function quicksort( a:Array<Dynamic>, ?comp:Comparator<Dynamic>, ?p:Int, ?q:Int ):Void
	{
		if ( p == null) p = 0;
		if (q == null ) q = a.length - 1;
		if ( comp == null ) comp = Comparators.getComparator( a[0] );
		Sorting.charlesHoare( a , comp, p, q );
	}
	
	public static function countingSort( a:Array<Dynamic>, min:Int, max:Int, ?comp:Comparator<Dynamic>, ?getKey:Dynamic->Int ):Bool
	{
		if ( comp == null )	comp = IntComparator.getInstance();
		if ( getKey == null )
		{
			getKey = function(i:Int){ return i; }
		}
		if ( Type.typeof( getKey(a[0]) ) != Type.typeof(0) )
				return false;// only integers!
		#if neko
		var c,tmp;
		untyped
		{
			c = __dollar__amake((max+1)-min);//var c:IntHash<Int> = new IntHash<Int>();
			tmp = __dollar__amake(a.length);//var tmp:Array<Dynamic> = new Array<Dynamic>();
		}
		var i;
		for ( i in 0...(max+1-min))//min...(max+1) )
		{
			c[i] = 0;//c.set(i-min,0);
		}
		for ( i in 0...a.length )
		{
			++c[getKey(a[i])-min];//c.set(getKey(a[i])-min,c.get(getKey(a[i])-min) + 1);
			tmp[i] = 0;
		}
		for ( i in 1...(max-min+1))
			c[i] += c[i-1];//c.set(i, c.get(i) + c.get(i-1));
		i = a.length - 1;
		while( i >= 0 )
		{
			tmp[c[getKey(a[i])-min]-1] = a[i];//tmp[c.get(getKey(a[i])-min)-1] = a[i];
			--c[getKey(a[i])-min];//c.set(getKey(a[i])-min,c.get(getKey(a[i])-min) - 1);
			--i;
		}
		#else true
		var c:Array<Int> = new Array<Int>();// max - min size Array
		var tmp:Array<Dynamic> = new Array<Dynamic>();//result holding Array
		var i;
		for ( i in min...(max+1) )
			c.push(0);
		for ( i in 0...a.length )
		{
			++c[getKey(a[i])-min];
			tmp.push(0);
		}
		for ( i in 1...c.length )
			c[i] += c[i-1];
		i = a.length - 1;
		while( i >= 0 )
		{
			tmp[c[getKey(a[i])-min]-1] = a[i];
			--c[getKey(a[i])-min];
			--i;
		}
		#end
		for ( i in 0...a.length )
			a[i] = tmp[i];
		
		return true;
	}
	
	public static function isSorted( it:Iterator<Dynamic>, ?comp:Comparator<Dynamic> )
	{
		if ( it.hasNext() )
		{
			var prev = it.next();
			if ( comp == null ) comp = Comparators.getComparator( prev );
			for ( i in it )
			{
				if ( comp.compare( prev, i ) > 0 )
				return false;
				prev = i;
			}
			return true;
		}else
			return false;
	}
	
	private static function charlesHoare(a:Array<Dynamic>, comp:Comparator<Dynamic>, p:Int, r:Int )
	{
		if ( r > p )
		{
			var i:Int = partition(a, comp, p, r );
			charlesHoare(a, comp, p, i-1);
			charlesHoare(a, comp, i+1, r);
		}
	}
	
	public static function partition(a:Array<Dynamic>, comp:Comparator<Dynamic>, p:Int, r:Int ):Int
	{
		var pivot:Int = r;
		var d:Int = p;
		var i:Int = p;
		var t;
		while( i < r )
		{
			if ( comp.compare(a[i], a[pivot]) < 0 ) 
			{
				t = a[i];a[i] = a[d];a[d] = t;//swap
				++d;
			}
			++i;
		}
		t = a[pivot];a[pivot] = a[d];a[d] = t;//swap
		return d;
	}
	
	private static function johnVonNeumann(a:Array<Dynamic>, comp:Comparator<Dynamic>, p:Int, r:Int )
	{
		if ( p < r )
		{
			var queue:Queue<Dynamic> = new Queue();
			var o;
			var i:Int = 0,j:Int = 1;
			var q:Int = (p+r)>>1;
			johnVonNeumann(a,comp,p,q);
			johnVonNeumann(a,comp,q + 1,r);
			
			//inline MERGE
			while( true )
			{
				if ( p + i <= q )
				{
					if( q + j <= r )
					{
						if ( comp.compare( a[p+i], a[q+j] ) <= 0 )
						{
							o = a[p+i];
							++i;
						}
						else
						{
							o = a[q+j];
							++j;
						}
					}
					else
					{
						o = a[p+i];
						++i;
					}
				}
				else if (  q + j <= r )
				{
					o = a[q+j];
					++j;
				}else
					break;
				
				queue.enqueue( o );
			}
			i = p;
			while( ! queue.isEmpty() )
			{
				var t =  queue.dequeue();
				a[i] = t;
				++i;
			}
		}
	}
	
	public static function main():Void
	{
		#if flash
			haxe.Firebug.redirectTraces();
		#end
		
		var getTime:Dynamic = haxe.util.benchmark.Timer.getTime;
		
		testSort(Sorting.mergeSort, getTime, "Merge sort");
		testSort(Sorting.quicksort, getTime, "Quicksort");
		testCountingSort(Sorting.countingSort, getTime, "Counting sort" );
	}
	
	public static function testSort( alg, getTime, ?n:String ):Void
	{
		if ( n == null ) n = "???";
		trace("Testing sorting : "+n+" algorythm");
		var t;
		var TIMES:Int = 10;
		var N:Int = 
			#if neko
			1000;
			#else true
			100;
			#end
		for ( test in 1...(TIMES+1) )
		{
		var a:Array<Int> = new Array<Int>();
		var b:Array<Int> = new Array<Int>();
		var tmp;
		for ( i in 0...(N*test) )
		{
			tmp = Math.round(Math.random()*(N*test));
			a.push( tmp );
			b.push( tmp );
		}
		
		trace("Test No "+test+" - "+(N*test)+" random values");
		var comp = IntComparator.getInstance();
		var c = comp.compare;
		t = getTime();
		b.sort( c );
		trace("Array build in sorting time : "+(getTime() - t ));
		t = getTime();
		alg(a, IntComparator.getInstance(), 0, a.length-1);
		trace(n+"   sorting time : "+(getTime() -  t));
		#if flash
		//trace("A:"+a.join("|"));
		//trace("B:"+b.join("|"));
		#end
		if ( ! isSorted( a.iterator() ) || ! isSorted( b.iterator() ) )
		//	trace("Array sorted properly");
		//else
			trace("ERROR - Array NOT sorted !!!");
		}
	}
	
	public static function testCountingSort( alg, getTime, ?n:String ):Void
	{
		if ( n == null ) n = "???";
		trace("Testing sorting : "+n+" algorythm");
		var t;
		var TIMES:Int = 10;
		var N:Int = 
			#if neko
			1000;
			#else true
			100;
			#end
		for ( test in 1...(TIMES+1) )
		{
		var a:Array<Int> = new Array<Int>();
		var b:Array<Int> = new Array<Int>();
		var tmp;
		for ( i in 0...(N*test) )
		{
			tmp = Math.round(Math.random()*(N*test));
			a.push( tmp );
			b.push( tmp );
		}
		
		trace("Test No "+test+" - "+(N*test)+" random values");
		var comp = IntComparator.getInstance();
		var c = comp.compare;
		t = getTime();
		b.sort( c );
		trace("Array build in sorting time : "+(getTime() - t ));//*/
		//trace("S:"+a.slice(0,20).join("|"));
		t = getTime();
		var f = function(i:Int){return i;}
		if (!alg(a, 0, Math.round(N*test), IntComparator.getInstance(), f ) )
			trace("Sorting ERROR - wrong data types");
		trace(n+"   sorting time : "+(getTime() -  t));
		#if flash
		//trace("A:"+a.slice(0,20).join("|"));
		//trace("B:"+b.slice(0,50).join("|"));
		#end
		if ( ! isSorted( a.iterator() ) )
			//trace("Array sorted properly");
		//else
			trace("ERROR - Array NOT sorted !!!");
		}
	}
	
}